package com.demo.其它;

/**
 * @author cl
 */
public class UnionFind {
    /**
     * 存储每个节点的前驱节点
     */
    private int[] pre;
    /**
     * 存储每个节点的高度
     */
    private int[] rank;

    public UnionFind(int[] pre, int[] rank) {
        if (pre == null || pre.length < 1 || rank == null || rank.length < 1) {
            throw new IllegalArgumentException("pre / rank参数无效!");
        }
        this.pre = pre;
        this.rank = rank;
    }

    /**
     * 查找代表元
     * 路径压缩算法 寻找过程中会将领导直接指向
     */
    public int find(int x) {
        if (pre[x] == x) {
            return x;
        }
        return pre[x] = find(pre[x]);
    }

    public boolean isSame(int x, int y) {
        return find(x) == find(y);
    }

    /**
     * 合并
     */
    public void union(int x, int y) {
        x = find(x);
        y = find(y);
        // 如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并，返回 false，表示合并失败；否则，执行下面的逻辑
        if (x == y) {
            return;
        }
        // 如果 x的高度大于 y，则令 y的上级为 x
        if (rank[x] > rank[y]) {
            pre[y] = x;
        } else {
            // 如果 x的高度和 y的高度相同，则令 y的高度加1
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
            // 让 x 的上级为 y
            pre[x] = y;
        }
    }
}
